﻿#pragma once
#include<iostream>
#include<assert.h>
using namespace std;

// 在二叉搜索树的基础上改变
// 插入一个节点只会影响祖先


// 节点类
template<class K,class V>
struct AVLTreeNode
{
	//K _key;// 节点数据
	AVLTreeNode<K,V>* _left;// 左孩子
	AVLTreeNode<K,V>* _right;// 右孩子
	AVLTreeNode<K,V>* _parent;// 父亲节点
	pair<K,V> _kv;// 数据
	int _bf;// 平衡因子



	// 构造函数
	AVLTreeNode(const pair<K,V>& kv)
		:_left(nullptr),
		_right(nullptr),
		_parent(nullptr),
		_bf(0),
		_kv(kv)
	{}

	
};


// AVLTree类
template<class K, class V>
class AVLTree
{
public:
	typedef AVLTreeNode<K, V> Node;

	// 插入
	bool Insert(const pair<K,V>& kv)
	{
		// 判断是否为空
		if (_root == nullptr)
		{
			// 插入的节点就时根节点
			_root = new Node(kv);
			return true;

		}

		//1.按照搜索树规则插入


		// _root不为空时，要从根节点开始向下查询
		// 记录父亲节点
		Node* parent = nullptr;
		Node* cur = _root;


		// 循环结束条件，查找到叶子节点
		while (cur)
		{
			// kv的first小于cur的first，查找左子数
			// 反之，查找右子树
			if (kv.first < cur->_kv.first)
			{
				parent = cur;// 记录父亲节点
				cur = cur->_left;
			}
			else if (kv.first > cur->_kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false;
			}
		}
		 

		// 找到插入的位置时
		cur = new Node(kv);

		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;


		// 插入完成后
		// 更新平衡因子
		// 2.更新插入节点的祖先节点的平衡因子
		// 由下向上更新
		// 这棵树的平衡因子定义为 平衡因子 = 右子树高度 - 左子树高度

		// 由下往上改平衡因子
		while (parent)
		{
			// a.插入父亲的左边，父亲的平衡因子--
			if (cur == parent->_left)
			{
				parent->_bf--;
			}
			else// b.插入父亲的右边，父亲的平衡因子++
			{
				parent->_bf++;
			}
			


			// 	c.更新后父亲的平衡因子 == 0，父亲所在子树高度不变，不再继续往上更新，插入结束
			if (parent->_bf == 0) // 1 -1 -> 0
			{
				// 更新完毕
				break;
			}
			// d.更新后父亲的平衡因子 == 1 or -1，父亲所在子 树高度变了，继续往上更新
			else if (parent->_bf == 1 || parent->_bf == -1) // 0 -> 1 -1
			{
				// 继续往上更新
				// 往上更新，将父亲给cur
				cur = parent;
				parent = parent->_parent;
			}
			// 	e.更新后父亲的平衡因子 == 2 or -2，父亲所在子树已经不平衡了，需要旋转处理
			else if (parent->_bf == -2 || parent->_bf == 2) // 1 -1 -> 2 -2
			{
				// 当前子树出问题了，需要旋转平衡一下
				if (parent->_bf == -2 && cur->_bf == -1)// 右单旋
				{
					RotateR(parent);
				}
				else if (parent->_bf == 2 && cur->_bf == 1)// 左单旋
				{
					RotateL(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == 1)// 左右单旋 
				{
					RotateLR(parent);
				}
				else if (parent->_bf == 2 && cur->_bf == -1)// 右左单旋
				{
					RotateRL(parent);
				}

				break;
			}
		}

		return true;

	}





	// 旋转只有看parent的节点
	// 右单旋
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;


		parent->_left = subLR;
		// 每个节点的父亲也要记得修改
		if (subLR != nullptr)
		{
			subLR->_parent = parent;
		}
		
		Node* ppNode = parent->_parent;
		subL->_right = parent;
		parent->_parent = subL;


		// 更新平衡因子
		// 注意两个关键情况：
		// 1.parent为根节点
		// 2.parent是第二层的节点

		if (parent == _root)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = subL;
			}
			else
			{
				ppNode->_right = subL;
			}

			subL->_parent = ppNode;
		}

		// 更新平衡因子
		parent->_bf = subL->_bf = 0;


	}

	// 左单旋
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		if (subRL != nullptr)
		{
			subRL->_parent = parent;
		}
		

		Node* ppNode = parent->_parent;
		
		subR->_left = parent;
		parent->_parent = subR;


		// 更新平衡因子
		// 注意两个关键情况：
		// 1.parent为根节点
		// 2.parent是第二层的节点
		if (parent == _root)
		{
			_root = subR ;
			subR->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = subR;
			}
			else
			{
				ppNode->_right = subR;

			}

			subR->_parent = ppNode;
		}

		// 更新平衡因子
		parent->_bf = subR->_bf = 0;

	}
	
	// 左右单旋
	void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		int bf = subLR->_bf;// 记录一下平衡因子

		// 先进行左单旋,在进行右单旋
		RotateL(subL);
		RotateR(parent);

		//更新平衡因子三种情况
		// 1.60自己就是新增
		if (bf == 0)
		{
			subLR->_bf = 0;
			subL->_bf = 0;
			parent->_bf = 0;
		}
		// 2.60的平衡因子为-1，b插入
		else if (bf == -1)
		{
			subLR->_bf = 0;
			subL->_bf = 0;
			parent->_bf = 1;
		}
		// 3.60的平衡因子为1，c插入
		else if (bf == 1)
		{
			subLR->_bf = 0;
			subL->_bf = -1;
			parent->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}
	
	// 右左单旋
	void RotateRL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		// 记录平衡因子
		int bf = subRL->_bf;

		// 先右旋，在左旋
		RotateR(subR);
		RotateL(parent);

		subRL->_bf = 0;
		// 更新平衡因子三种情况
		// 1.60自己就是新增
		if (bf == 0)
		{
			subR->_bf = 0;
			parent->_bf = 0;
		}
		// 2.60的平衡因子为-1，b插入
		else if (bf == -1)
		{
			subR->_bf = 1;
			parent->_bf = 0;
		}
		// 3.60的平衡因子为1，c插入
		else if (bf == 1)
		{
			subR->_bf = 0;
			parent->_bf = -1;
		}
		else
		{
			assert(false);
		}
	}


	// 查找
	Node* Find(const K &key)
	{
		// 由头节点开始查找
		Node* cur = _root;
		Node* parent = nullptr;

		while (cur)
		{
			if (key < cur->_kv.first)
			{
				parent = cur;
				cur = cur->_left;// 向左查找
			}
			else if (key > cur->_kv.first)
			{
				parent = cur;
				cur = cur->_right;// 向右查找
			}
			else// 相等则找到
			{
				return cur;
			}
		}

		return nullptr;

	}

	// 中序输出
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
	// 判断平衡
	bool IsBalance()
	{
		return _IsBalance(_root);
	}
	//计算高度
	int Height()
	{
		return _Height(_root);
	}
	// 节点数量
	int Size()
	{
		return _Size(_root);
	}
	
private:
	 
	// 计算节点个数基本
	int _Size(Node* root)
	{
		if (root == nullptr)
		{
			return 0;
		}

		return _Size(root->_left) + _Size(root->_right) + 1;
	}

	// 计算高度基本
	int _Height(Node* root)
	{
		if (root == nullptr)
		{
			return 0;
		}

		return max(_Height(root->_left), _Height(root->_right)) + 1;
	}


	// 判断平衡基本
	bool _IsBalance(Node* root)
	{
		if (root == nullptr)
		{
			return true;
		}

		int leftHight = _Height(root->_left);
		int rightHight = _Height(root->_right);

		// 不平衡
		if (abs(rightHight - leftHight) >= 2)
		{
			return false;
		}

		// 顺便检查一下平衡因子是否正确
		if (rightHight - leftHight != root->_bf)
		{
			cout << root->_kv.first << endl;
			return false;
		}

		// 判断左子树和右子树是否平衡
		return _IsBalance(root->_left)
			&& _IsBalance(root->_right);
	}

	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		_InOrder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_InOrder(root->_right);

	}

	Node* _root = nullptr;// 根节点
};